class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

class Solution {
    public int maxHighTree(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxHighTree(root.left);
        int right=maxHighTree(root.right);
        if(left>=0&&right>=0&&Math.abs(left-right)<2){
            return Math.max(left,right);
        }
        return -1;
    }
    public boolean isBalanced(TreeNode root) {
        return maxHighTree(root)<0?false:true;
    }







    public boolean isSametree(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }else if(left==null||right==null){
            return false;
        }else if(left.val!=right.val){
            return false;
        }else {
            return isSametree(left.left,right.left)&&isSametree(left.right,right.right);
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null){
            return false;
        }
        if(isSametree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
}